Real-time video has become increasingly popular to users. In order to achieve real-time video, computational intensive video coding techniques have been developed to compress the video. One common type of video compression is a motion-compensation-based video coding scheme. This type of video compression is used in coding standards such as MPEG-1, MPEG-2, MPEG-4, H.261, H.263, and H.264.
These motion-compensation-based video coding schemes have been quite successful in providing real-time video conferencing capabilities on personal computers. However, the coding schemes are too computational complex for operating on mobile devices, such as handheld computers, cellular phones with built in digital cameras, and the like. The mobile devices do not have sufficient computation power, battery power, and memory for processing these real-time video coding schemes.
Most of the complexity in these video coding schemes is attributed to a process called motion estimation. In general, motion estimation removes temporal (i.e., time) redundancy between video frames. Video frames are divided into several macroblocks, where a macroblock represents an N×N array of pixels (e.g., 16 pixels by 16 pixels). The temporal redundancy is removed by computing a motion vector for each macroblock. The motion vector represents a translational displacement of the macroblock between frames. In other words, each motion vector describes the distance that a macroblock has moved from a previous frame and the direction in which the macroblock has moved. The motion vectors for the macroblocks are then transmitted in the video stream instead of the entire macroblock, thereby reducing the amount of data in the video stream.
There have been significant advances in fast motion estimation techniques that reduce the computational complexity of determining motion vectors. Some of these fast motion estimation techniques are described in the following articles:    R. Li, B. Zeng, and M. L. Liou, “A new three-step search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 4, no. 4, pp. 438-442, August 1994;    S. Zhu and K. K. Ma, “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Transactions on Image Processing, vol. 9, no. 2, pp. 287-290, February 2000;    A. M. Tourapis, O. C. Au, and M. L. Liou, “Highly efficient predictive zonal algorithms for fast block-matching motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 10, pp. 934-947, October 2002; and    A. Chimienti, C. Ferraris, and D. Pau, “A complexity-bounded motion estimation algorithm,” IEEE Transactions on Image Processing, vol. 11, no. 4, pp. 387-392, April 2002.
There has also been some development in computational-complexity scalable motion estimation techniques that are directed at further reducing the complexity of fast motion estimation. Some of these computational-complexity scalable motion estimation techniques are described in the following articles:    K. Lengwehasatit and A. Ortega, “Computationally scalable partial distance based fast search motion estimation,” Proceeding of International Conference on Image Processing, vol. 1, pp. 824-827, September 2000; and    S. Mietens, P. H. N. de With, and C. Hentschel, “Computational-complexity scalable motion estimation for mobile MPEG encoding,” IEEE Transactions on Consumer Electronics, vol. 50, no. 1, pp. 281-291, February 2004.
Even with these advances, there is still a need for an improved motion estimation technique that is scalable based on the available computation resources of a device.